/*
练习15-5 带权的活动安排问题
分数 30
作者 陈越
单位 浙江大学

假设只有一间活动室可用，现有 n
个俱乐部来申请使用，每个俱乐部的活动都有一个计划开始的时间和结束的时间，并且每个俱乐部的活动还有一个权重。要求审批通过的所有活动在时间安排上不能有冲突（即前一个活动的结束时间不迟于后一个活动的开始时间），并且通过的所有俱乐部的总权重和最大。请设计算法解决这个问题。
函数接口定义：

int WeightedActivitySelection(Activities a, int n);

其中 Activities 类型的定义如下：

typedef struct ActivityNode *Activities;
struct ActivityNode {
    int start;  //  开始时间
    int finish; //  结束时间
    int weight; //  权重
};

函数接口定义中，a 是存放活动集合的数组，共有 n 个活动，并且按 finish
的非递减序存放。其中 a[0]  是一个虚设的活动，其开始、结束时间和权重均为
0。要求函数 WeightedActivitySelection 返回最优解的总权重和。

输入样例：

17
2 3 2
4 5 1
1 6 1
7 17 2
16 19 3
18 28 2
29 35 1
34 37 1
34 37 1
34 37 3
36 43 1
42 45 1
44 57 2
56 59 1
56 59 1
56 59 1
58 66 1

输出样例：

13
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct ActivityNode *Activities;
struct ActivityNode {
    int start;  /* 开始时间 */
    int finish; /* 结束时间 */
    int weight; /* 权重 */
};

int WeightedActivitySelection(Activities a, int n);

int CmpFinish(const void *a, const void *b) {
    return (((const struct ActivityNode *)a)->finish >
            ((const struct ActivityNode *)b)->finish)
               ? 1
               : -1;
}

int main(void) {
    Activities a;
    int n, i;

    scanf("%d", &n);
    a = (Activities)malloc(sizeof(struct ActivityNode) * (n + 1));
    a[0].finish = 0; /* a[0] 是一个虚设的活动，其结束时间为 0 */
    a[0].start = 0;
    a[0].weight = 0;
    for (i = 1; i <= n; i++) {
        scanf("%d %d %d", &a[i].start, &a[i].finish, &a[i].weight);
    }
    qsort(a, n + 1, sizeof(struct ActivityNode), CmpFinish);
    printf("%d", WeightedActivitySelection(a, n));

    return 0;
}
/* 你的代码将被嵌在这里 */

/*
动态规划计算：

对于每个活动 i，找到与当前活动 i 不冲突的最后一个活动 j。
使用动态规划转移方程计算 dp[i]：
dp[i] = max(dp[j] + a[i].weight, dp[i - 1])
其中 dp[j] + a[i].weight 表示选择当前活动 i 的权重和。
dp[i - 1] 表示不选择当前活动 i 的权重和。
*/
int WeightedActivitySelection(Activities a, int n) {
    int i, j, *dp, max_weight;

    dp = (int *)malloc(sizeof(int) * (n + 1)); // 分配动态规划数组
    dp[0] = 0; // 初始化虚设活动的权重为0

    // 计算每个活动的最优解
    for (i = 1; i <= n; i++) {
        // 找到与当前活动 i 不冲突的最后一个活动 j
        for (j = i - 1; j >= 0; j--) {
            if (a[j].finish <= a[i].start) {
                break;
            }
        }
        // 动态规划转移方程：dp[i] = max(dp[j] + a[i].weight, dp[i - 1])
        dp[i] = (dp[j] + a[i].weight) > dp[i - 1] ? (dp[j] + a[i].weight) : dp[i - 1];
    }

    max_weight = dp[n]; // 最优解的总权重和
    free(dp); // 释放动态规划数组

    return max_weight; // 返回最优解的总权重和
}